/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年05月12日
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
================================================================*/


#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int size = nums.size();
        if( size == 0 )
            return 0;

        int** dp = new int*[size];
        for(int i = 0; i < size; i++){
            dp[i] = new int[size];
            for(int j = 0; j < size; j++)
                if(j == i)
                    dp[i][j] = nums[i];
                else
                    dp[i][j] = 1;
        }

        int maxres = INT_MIN;
        for(int k = size - 1; k >= 0; k--){
            maxres = max(maxres, dp[k][k]); 
            for(int j = k - 1; j >= 0; j--){
                dp[j][k] = nums[j] * dp[j+1][k];
                maxres = max(maxres, dp[j][k]); 
            }
        }

        for(int i = 0; i < size; i++)
            delete[] dp[i];

        delete[] dp;

        return maxres;
    }
};

class Solution {
public:
    int maxProduct(vector<int>& nums) {
     	int size = nums.size();
        if(size == 0)
            return 0;
        
        int imin = 1, imax = 1, maxres = INT_MIN;
        int tmp;
        for(int i = 0; i < size; i++){
            if(nums[i] < 0){
                tmp = imin;
                imin = imax;
                imax = tmp;
            }

            imax = max(nums[i]*imax, nums[i]);
            imin = min(nums[i]*imin, nums[i]);
            maxres = max(maxres, imax);
        }

        return maxres;
    }
};

